// 《围棋》作者版权所有。版权所有。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

// 此文件实现类型统一。

package types

import (
	"bytes"
	"go/token"
	"sort"
)

// unifier维护两组独立的类型参数x和y 
// 用于解析提供给UNIFED调用的x和y参数
// 中的类型参数。对于单向统一，只提供其中一个集合（比如x），然后类型参数是
// 只为传递给UNIFED的x参数解析，而不是y参数
// （即使可能也包含相同的类型参数）。这个
// 对于推断自递归调用的类型参数是至关重要的：
// 
// func f[P any]（a P）{f（a）}
// 
// 对于调用f（a），我们想推断P的类型参数是P.
// 在统一过程中，参数类型P必须解析为类型
// 参数P（“x”侧），但参数类型P必须单独保留，以便
// 统一将类型参数P解析为P。
// 
// 对于双向统一，提供两个集。这使得
// 统一可以从参数类型转换为参数类型，反之亦然。
// 对于约束类型推断，我们使用双向统一
// 其中x和y类型参数相同。这是通过设置其中一个（使用init），然后将其值
// 分配给另一个来实现的。

// 统一程序维护x和y的当前类型参数
// 以及为每个类型参数推断的相应类型。
// 通过调用newUnifier创建unifier。
type unifier struct {
	check *Checker
	exact bool
	x, y  tparamsList // x和y必须通过tparamsList.init初始化
	types []Type      // 由x和y共享的推断类型
}

// newUnifier返回一个新的unifier。
// 如果设置了exact，则统一要求统一类型与
// 完全匹配。如果未设置exact，则如果统一失败，则会考虑命名类型的基础类型
// 并忽略通道的
// 方向。
func newUnifier(check *Checker, exact bool) *unifier {
	u := &unifier{check: check, exact: exact}
	u.x.unifier = u
	u.y.unifier = u
	return u
}

// unify尝试统一x和y，并报告是否成功。
func (u *unifier) unify(x, y Type) bool {
	return u.nify(x, y, nil)
}

// tparamsList描述类型参数列表以及为其推断的类型。
type tparamsList struct {
	unifier *unifier
	tparams []*TypeName
	// 对于每个tparams元素，索引中都有一个对应的类型插槽索引。
	// 索引<0:unifier.types[-index-1]==nil 
	// 索引==0:尚未分配类型槽
	// 索引>0:unifier.types[index-1]==typ 
	// 连接的tparams元素共享相同的类型槽，因此具有相同的索引。
	// 通过对nil类型使用负索引，我们不需要检查unifier.types 
	// 来查看是否有类型。
	indices []int // len（d.index）=len（d.tparams）
}

// String返回tparamsList的字符串表示形式。用于调试。
func (d *tparamsList) String() string {
	var buf bytes.Buffer
	buf.WriteByte('[')
	for i, tname := range d.tparams {
		if i > 0 {
			buf.WriteString(", ")
		}
		writeType(&buf, tname.typ, nil, nil)
		buf.WriteString(": ")
		writeType(&buf, d.at(i), nil, nil)
	}
	buf.WriteByte(']')
	return buf.String()
}

// init使用给定的类型参数初始化d。
// 类型参数必须按照它们在声明中出现的顺序
// （这确保tparams索引与相应的类型参数索引匹配）。
func (d *tparamsList) init(tparams []*TypeName) {
	if len(tparams) == 0 {
		return
	}
	if debug {
		for i, tpar := range tparams {
			assert(i == tpar.typ.(*_TypeParam).index)
		}
	}
	d.tparams = tparams
	d.indices = make([]int, len(tparams))
}

// join将x的第i个类型参数与y的第j个类型参数统一起来。
// 如果两个类型参数已经有一个与之关联的类型，并且它们是
// 未联接，则联接失败并返回false。
func (u *unifier) join(i, j int) bool {
	ti := u.x.indices[i]
	tj := u.y.indices[j]
	switch {
	case ti == 0 && tj == 0:
		// 两个类型参数都没有与其关联的类型槽。
		// 分配一个新的联接的nil类型插槽（负索引）。
		u.types = append(u.types, nil)
		u.x.indices[i] = -len(u.types)
		u.y.indices[j] = -len(u.types)
	case ti == 0:
		// x的类型参数还没有类型槽。使用y形槽。
		u.x.indices[i] = tj
	case tj == 0:
		// y的类型参数还没有类型槽。使用x的插槽。
		u.y.indices[j] = ti

	// 两个类型参数都有一个插槽：ti！=0&&tj！=0
	case ti == tj:
		// 两个类型参数已共享同一个插槽。无事可做。
		break
	case ti > 0 && tj > 0:
		// 两个类型参数都有推断类型（可能不同）。无法加入。
		return false
	case ti > 0:
		// 只有x的类型参数具有推断类型。用x槽代替y槽。
		u.y.setIndex(j, ti)
	default:
		// y的类型参数有推断类型，或者类型
		// 参数都没有推断类型。在任何一种情况下，使用y槽作为x槽。
		u.x.setIndex(i, tj)
	}
	return true
}

// 如果typ是d的类型参数，则index返回类型参数index。
// 否则，结果为<0。
func (d *tparamsList) index(typ Type) int {
	if t, ok := typ.(*_TypeParam); ok {
		if i := t.index; i < len(d.tparams) && d.tparams[i].typ == t {
			return i
		}
	}
	return -1
}

// /setIndex将第i个类型参数
// （及其所有关联参数）的类型槽索引设置为tj。类型参数
// 必须有一个（可能为零）类型的插槽与其关联。
func (d *tparamsList) setIndex(i, tj int) {
	ti := d.indices[i]
	assert(ti != 0 && tj != 0)
	for k, tk := range d.indices {
		if tk == ti {
			d.indices[k] = tj
		}
	}
}

// at返回为第i个类型参数设置的类型；或者零。
func (d *tparamsList) at(i int) Type {
	if ti := d.indices[i]; ti > 0 {
		return d.unifier.types[ti-1]
	}
	return nil
}

// set设置第i个类型参数的类型类型；
// 类型不能为零，也不能在以前设置过。
func (d *tparamsList) set(i int, typ Type) {
	assert(typ != nil)
	u := d.unifier
	switch ti := d.indices[i]; {
	case ti < 0:
		u.types[-ti-1] = typ
		d.setIndex(i, -ti)
	case ti == 0:
		u.types = append(u.types, typ)
		d.indices[i] = len(u.types)
	default:
		panic("type already set")
	}
}

// types返回类型参数
// 的推断类型列表（通过统一）和索引。如果推断出所有类型，则返回的索引小于0。
// 否则为第一个类型参数的索引，无法推断；
// 即列表[索引]为零。
func (d *tparamsList) types() (list []Type, index int) {
	list = make([]Type, len(d.tparams))
	index = -1
	for i := range d.tparams {
		t := d.at(i)
		list[i] = t
		if index < 0 && t == nil {
			index = i
		}
	}
	return
}

func (u *unifier) nifyEq(x, y Type, p *ifacePair) bool {
	return x == y || u.nify(x, y, p)
}

// nify实现了核心统一算法，这是一个
// Checker.identical0的改编版本。对于
// 代码的更改，应在此处进行相应的更改。
// 不能直接从unifier外部调用。ABCFDG
func (u *unifier) nify(x, y Type, p *ifacePair) bool {
	x = expand(x)
	y = expand(y)

	if !u.exact {
		// （微妙：我们使用isNamed包含任何具有名称的类型（包括
		// 基本类型和类型参数。我们使用asNamed（），因为我们只需要
		// 需要*命名类型。）
		switch {
		case !isNamed(x) && y != nil && asNamed(y) != nil:
			return u.nify(x, under(y), p)
		case x != nil && asNamed(x) != nil && !isNamed(y):
			return u.nify(under(x), y, p)
		}
	}

	// 至少有一个x或y是类型参数的情况。
	switch i, j := u.x.index(x), u.y.index(y); {
	case i >= 0 && j >= 0:
		// x和y都是类型参数
		if u.join(i, j) {
			return true
		}
		// x和y都有推断类型-它们必须匹配
		return u.nifyEq(u.x.at(i), u.y.at(j), p)

	case i >= 0:
		// x是类型参数，y不是
		if tx := u.x.at(i); tx != nil {
			return u.nifyEq(tx, y, p)
		}
		// 否则，从y推断类型
		u.x.set(i, y)
		return true

	case j >= 0:
		// y是类型p参数，x不是
		if ty := u.y.at(j); ty != nil {
			return u.nifyEq(x, ty, p)
		}
		// 否则，从x 
		u.y.set(j, x)
		return true
	}

	// 推断类型以实现类型统一，对于相同的
	// 类型，不要使用快捷方式（x==y）。相反，保持按元素比较，以统一
	// 匹配（和相等的类型参数类型）一个简单的测试用例
	// 其中重要的是：func f[P any]（ap）{f（A）}.

	switch x := x.(type) {
	case *Basic:
		// 除了符文和字节
		// 别名之外，基本类型都是单例，因此我们不能仅仅依赖上面的x==y检查
		// 也请参见TypeName.IsAlias中的注释。
		if y, ok := y.(*Basic); ok {
			return x.kind == y.kind
		}

	case *Array:
		// 如果两个数组类型具有相同的元素类型
		// 并且相同数组长度。
		if y, ok := y.(*Array); ok {
			// 如果一个或两个数组长度未知（<0）由于某些错误，
			// 假定它们是相同的，以避免出现虚假的后续错误。
			return (x.len < 0 || y.len < 0 || x.len == y.len) && u.nify(x.elem, y.elem, p)
		}

	case *Slice:
		// 如果两个切片类型具有相同的元素类型，则它们是相同的。
		if y, ok := y.(*Slice); ok {
			return u.nify(x.elem, y.elem, p)
		}

	case *Struct:
		// 如果两个结构类型具有相同的字段序列，则它们是相同的，
		// 如果相应的字段具有相同的same名称和相同的类型，
		// 和相同的标记。两个嵌入字段被视为具有相同的
		// 名称。来自不同包的小写字段名称始终不同。
		if y, ok := y.(*Struct); ok {
			if x.NumFields() == y.NumFields() {
				for i, f := range x.fields {
					g := y.fields[i]
					if f.embedded != g.embedded ||
						x.Tag(i) != y.Tag(i) ||
						!f.sameId(g.pkg, g.name) ||
						!u.nify(f.typ, g.typ, p) {
						return false
					}
				}
				return true
			}
		}

	case *Pointer:
		// 如果两个指针类型具有相同的基类型，则它们是相同的。
		if y, ok := y.(*Pointer); ok {
			return u.nify(x.base, y.base, p)
		}

	case *Tuple:
		// 两个元组类型如果它们具有相同数量的元素
		// 则相同，并且相应的元素具有相同的类型。
		if y, ok := y.(*Tuple); ok {
			if x.Len() == y.Len() {
				if x != nil {
					for i, v := range x.vars {
						w := y.vars[i]
						if !u.nify(v.typ, w.typ, p) {
							return false
						}
					}
				}
				return true
			}
		}

	case *Signature:
		// 如果它们具有相同数量的参数
		// 并且结果值、相应的参数和结果类型相同，则两个函数类型相同，
		// 和e两个函数是否都是可变的。参数和结果
		// 名称不需要匹配。
		// TODO（gri）处理类型参数或记录我们可以忽略它们的原因。
		if y, ok := y.(*Signature); ok {
			return x.variadic == y.variadic &&
				u.nify(x.params, y.params, p) &&
				u.nify(x.results, y.results, p)
		}

	case *_Sum:
		// 当前内部使用sum类型时不应发生这种情况。
		panic("type inference across sum types not implemented")

	case *Interface:
		// 如果两个接口类型具有与
		// 相同的方法集，则它们是相同的。相同的名称和相同的函数类型。ABCDEF中的小写方法名称G
		if y, ok := y.(*Interface); ok {
			// 间接调用identical0 
			// （例如Identical、IdenticalIgnoreTags等），check为nil。但是在这种情况下，接口应该是完整的，而延迟完成
			// 这里不需要。
			if u.check != nil {
				u.check.completeInterface(token.NoPos, x)
				u.check.completeInterface(token.NoPos, y)
			}
			a := x.allMethods
			b := y.allMethods
			if len(a) == len(b) {
				// 接口类型是唯一可以发生循环的类型
				// 没有“终止”通过命名类型；此类循环
				// 只能通过
				// 匿名接口（直接或间接）嵌入
				// 当前接口的方法参数类型创建。示例：
				// 
				// 类型T接口{
				// m（）接口{T}
				// }
				// 
				// 如果比较两个这样的（不同名称的）接口，
				// 如果未检测到循环，则会发生无休止的递归。
				// 
				// 如果之前比较过x和y，则它们必须相等
				// （如果不是，则递归将停止）；
				// 在ifacePair堆栈中搜索同一对。
				// 
				// 这是一个二次算法，但在实践中，这些堆栈
				// 非常短（以接口
				// 的嵌套深度为界，通过参数类型重复出现的类型声明非常罕见）。另一种实现可能使用
				// /“已访问”映射，但总体效率可能较低。
				q := &ifacePair{x, y, p}
				for p != nil {
					if p.identical(q) {
						return true // 在
					}
					p = p.prev
				}
				if debug {
					assert(sort.IsSorted(byUniqueMethodName(a)))
					assert(sort.IsSorted(byUniqueMethodName(b)))
				}
				for i, f := range a {
					g := b[i]
					if f.Id() != g.Id() || !u.nify(f.typ, g.typ, q) {
						return false
					}
				}
				return true
			}
		}

	case *Map:
		// 之前对同一对进行了比较。如果两个映射类型具有相同的键和值类型，则它们是相同的。
		if y, ok := y.(*Map); ok {
			return u.nify(x.key, y.key, p) && u.nify(x.elem, y.elem, p)
		}

	case *Chan:
		// 如果两个通道类型具有相同的值类型，则它们是相同的。
		if y, ok := y.(*Chan); ok {
			return (!u.exact || x.dir == y.dir) && u.nify(x.elem, y.elem, p)
		}

	case *Named:
		// 如果两个命名类型的类型名源自同一类型声明中的
		// 则它们是相同的。
		// 如果是，则ok:=y.（*命名）；ok{
		// 返回x.obj==y.obj 
		// /}
		if y, ok := y.(*Named); ok {
			// /TODO（gri）这并不总是正确的：如果其中一个类型嵌套在函数中，则两个类型可能在同一个包中具有相同的名称
			// 。
			// 可能性极低，但我们需要一个始终正确的解决方案。
			if x.obj.pkg == y.obj.pkg && x.obj.name == y.obj.name {
				assert(len(x.targs) == len(y.targs))
				for i, x := range x.targs {
					if !u.nify(x, y.targs[i], p) {
						return false
					}
				}
				return true
			}
		}

	case *_TypeParam:
		// 两个类型参数（不属于
		// 封闭类型的类型参数的一部分，如本函数开头所述）
		// 如果它们源自同一声明，则它们是相同的。
		return x == y

	// 案例*实例：
	// 由于类型已扩展，因此无法访问

	case nil:
		// 避免在无类型

	default:
		u.check.dump("### u.nify(%s, %s), u.x.tparams = %s", x, y, u.x.tparams)
		unreachable()
	}

	return false
}
